/**
 * \file Base.cpp
 * \brief Base class implementation and misc functions
 * \author Wouter Caarls <w.caarls@tnw.tudelft.nl>
 *
 * \verbatim
 * Copyright (c) 2005 Wouter Caarls, Delft University of Technology
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * \endverbatim
 */

/** \page devdoc The Structure of PEPCI
\section A Brief Overview
PEPCI has three separate class hierarchies: Code, Type, and Symbol. There are also three basic operations: reduce, residualize, and toString. When the program is started, the input is first parsed by parseATerm into a Code object. This object is then reduced, which does the actual interpretation. reduce operates recursively, first determining the Type, and then doing the necessary calculations. Declarations and assignments are put into a SymbolTable.

A second output of reduce is a Compound with the parts of the program that couldn't be interpreted. All declarations and assignments are put into this Compound in a tentative state, and can be marked untentative by the residualize function. This function is called when an assignment or control structure couldn't be resolved, before putting the control structure itself into the Compound. In this way, scoping problems are avoided.

After the reduction has completed, the output is converted into c code again using toString. This code can then be passed to a C compiler, generally running faster than the original code.
 */

/** \page langdoc The PEPCI language
 *
 * PEPCI is both a subset and superset of the C language. In the next two sections, the
 * difference between PEPCI and C is explained.
 *
 * \section subset C constructs not supported in PEPCI
 * \subsection Keywords
 * \li \c auto
 * \li \c case
 * \li \c const
 * \li \c continue
 * \li \c default
 * \li \c enum
 * \li \c extern
 * \li \c goto
 * \li \c inline
 * \li \c register
 * \li \c restrict
 * \li \c static
 * \li \c switch
 * \li \c union
 * \li \c volatile
 * \li \c _Bool
 * \li \c _Complex
 * \li \c _Imaginary
 *
 * \subsection Constructs
 * \li <em>Bitwise operations</em>: <tt>& | ^ ~ << >></tt>
 * \li <em>Updating assignments</em>: <tt>*= /= %= += -= <<= >>= &= ^= |=</tt>
 * \li <em>Conditional expressions</em>: <tt>?</tt>
 * \li <em>Comma operator</em>: <tt>,</tt>
 * \li <em>Member dereference</em>: <tt>-></tt>
 * \li <em>Functions with variable number of arguments</em>: <tt>...</tt>
 * \li <em>Array initializers</em>: <tt>{ , , ... , }</tt>
 * \li <em>Function pointers</em>: <tt>void (*a)(void)</tt>
 * \li <em>Named structs</em>: <tt>struct a</tt>
 * 
 * \subsection Semantics
 * 
 * \li \c return does not exit a function, but a loop.
 * \li The syntax should be context-free. This means there must be no ambiguities that
 *     can only be resolved by using a symbol table.
 * \li The formal and actual parameters of a function must not clash.
 * \li PEPCI does not support multiple sourcefiles. Instead, the \c extern
 *     keyword specifies that a function should be located and called
 *     in a foreign function library.
 * \li The \c auto, \c static, \c volatile and \c restrict keywords are passed through but not interpreted.
 *
 * \section superset Additional constructs
 * \subsection Keywords
 * \li \c promote storage class. Declarations with this class are promoted to the first enclosing compound that has declarations
 *     (unless such is not available). This means variables can be declared in loops.
 * \li \c code %Code type. Variables of this type contain (Abstract Syntax Tree representations of) C code.
 * \li \c strategy Strategy definitions. A function may be defined as being a strategy
 *     by omitting any type specifiers and using the \c strategy qualifier. A strategy
 *     is not evaluated, but rather all references to formal arguments are replaced
 *     by the actual arguments, and the resulting \c code is returned.
 *     Example: \code strategy doStuff(code a) { print(a); } \endcode
 * \li \c stratego Inline stratego definitions. Stratego rewrite strategies can be
 *     defined inline, like a function. In the definition, a main strategy should be
 *     defined. The function arguments are available as pre-bound variables
 *     everywhere in the function, but should not be used as match templates.
 *     They are also passed to the main strategy in a tuple (unless the
 *     function has only one argument). For example:
\code
stratego equals(code a, code b)
{
  strategies
    main = (?(v, v); !|[1]|) <+ !|[0]|
}
\endcode
 *
 * \subsection Constructs
 * \li <em>%Code constants</em>: A piece of program code may be encapsulated as \c code
 *     by surrounding it by backtics.
* \li <em>%Code antiquotation</em>: By using the escape operator $, an expression may be inserted in a code constant.
  * \li <em>%Code evaluation</em>: \c code variables may be evaluated using the code dereference operator @:
\code
code greet = `printf("Hello, world!\n");`;
@greet;
\endcode
 * \li <em>Function constructs</em>: A function with a \c code argument as the last argument
 *     may be called like a construct such as \c while. This makes certain strategy
 *     calls more readable.
 *     Example: \code replace(`a`, `*a`) { a = 12; } \endcode
 */
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>

#include "CStr.h"
#include "Base.h"
#include "Symbol.h"
#include "Value.h"
#include "Code.h"
#include "Expression.h"

#define PATH_MAX 512

/** \brief Main PEPCI logging object */
PLog plog;

/** \brief Pointer to last statement encountered by \em reduce. */
std::string g_lastStatement;

bool g_outputTentative;
int g_codes=0;

void setLastStatement(Code *code)
{
  g_lastStatement = code->toString();
}

void _error(const char *file, const int line, const char *function, const char *msg)
{
  std::cerr << "Error:     " << msg << std::endl;
  std::cerr << "Statement: " << g_lastStatement;
  std::cerr << "Function:  " << function << " at " << file << ":" << line << std::endl;
  exit(1);
}

std::string indent(int indentation, char *separator)
{
  CStr res;

  for (int i=0; i != indentation; ++i)
    res << separator;

  return (char*)res;
}

int popen2(const char *command, int *filedes)
{
  return popen2a(command, "", filedes);  
}

int popen2a(const char *command, char *args, int *filedes)
{
  int fromchild[2], tochild[2];
  int res;
  char *newargs = new char[strlen(args)+1];
  char *argarr[256];
  int i=0;

  LOG(plog.crawl, HDR << "Opening pipes to process '" << command << "'" << std::endl);

  strcpy(newargs, args);

  argarr[i++] = (char*)command;
  if ((argarr[i++] = strtok(newargs, " ")))
    while ((argarr[i++] = strtok(NULL, " ")));

  if ((res = pipe(fromchild))) return res;
  if ((res = pipe(tochild))) return res;
  
  if ((res = fork()))
  {
    /* Parent */
    if (res < 0) return res;

    close(fromchild[1]);
    close(tochild[0]);

    filedes[0] = fromchild[0];
    filedes[1] = tochild[1];

    return 0;
  }
  else
  {
    /* Child */
    close(tochild[1]);
    close(fromchild[0]);

    dup2(tochild[0], STDIN_FILENO);
    dup2(fromchild[1], STDOUT_FILENO);

    execvp(command, argarr);

    plog.err() << HDR << "Couldn't exec " << command << " " << args << std::endl;

    exit(1);
  }
}

int fileCompare(char *name1, char *name2)
{
  FILE *f1, *f2;
  unsigned int count;
  int res;
  char buf1[PATH_MAX], buf2[PATH_MAX];

  if (!(f1=fopen(name1, "r"))) return -1;
  if (!(f2=fopen(name2, "r")))
  {
    fclose(f1);
    return 1;
  }

  while ((count=fread(buf1, 1, PATH_MAX, f1)))
  {
    if (fread(buf2, 1, PATH_MAX, f2) != count)
    {
      fclose(f1); fclose(f2);
      return 1;
    }

    if ((res = memcmp(buf1, buf2, count)))
    {
      fclose(f1); fclose(f2);
      return res;
    }
  }

  if ((count=fread(buf2, 1, PATH_MAX, f2)))
  {
    fclose(f1); fclose(f2);
    return -1;
  }

  return 0;
}

int fileDateCompare(char *name1, char *name2)
{
  struct stat sbuf1, sbuf2;

  if (stat(name1, &sbuf1)) return -1;
  if (stat(name2, &sbuf2)) return 1;

  if (sbuf1.st_mtime > sbuf2.st_mtime)
    return 1;
  if (sbuf1.st_mtime < sbuf2.st_mtime)
    return -1;
  return 0;
}

/* ************************************************************************* */

void Value::residualize(SymbolTable *symbols, bool markUnknown)
{
  if (!declarations.empty())
  {
    std::vector<Declaration2*> _declarations = declarations;
    declarations.clear();

    LOG(plog.crawl, HDR << "residualizing declarations" << std::endl);

    for (DI ii=_declarations.begin(); ii != _declarations.end(); ++ii)
    {
      LOG(plog.crawl, HDR << "residualizing " << (*ii)->toTerm() << std::endl);
      (*ii)->residualize(symbols);
    }
  }

  if (!assignments.empty())
  {
    std::vector<Stat*> _assignments = assignments;
    assignments.clear();

    LOG(plog.crawl, HDR << "residualizing assignments" << std::endl);

    for (AI ii=_assignments.begin(); ii != _assignments.end(); ++ii)
    {
      LOG(plog.crawl, HDR << "residualizing " << (*ii)->toTerm() << std::endl);
      (*ii)->residualize(symbols);
    }
  }

  if (markUnknown)
    known = false;
}

void Value::adddeclaration(Declaration2 *declaration)
{
  LOG(plog.crawl, HDR << "adding declaration " << declaration << " ("
                      << declaration->refcount << ") to "
                      << this << std::endl);
  declarations.push_back(declaration);
  declaration->refcount++;

  /* Can't be sure of reference count for pointer values */
  if (typeid(*this) == typeid(PointerValue))
    declaration->refcount++;
}

void Value::addassignment(Stat *assignment)
{
  LOG(plog.crawl, HDR << "adding assignment " << assignment << " ("
                      << assignment->refcount << ") to "
                      << this << std::endl);
  assignments.push_back(assignment);
  assignment->refcount++;
  
  /* Can't be sure of reference count for pointer values */
  if (typeid(*this) == typeid(PointerValue))
    assignment->refcount++;
}

void Value::cleardeclarations(void)
{
  if (!declarations.empty())
  {
    LOG(plog.crawl, HDR << "clearing declarations of " << this << std::endl);

    for (DI ii=declarations.begin(); ii != declarations.end(); ++ii)
      (*ii)->clear();
  }

  declarations.clear();
}

void Value::clearassignments(void)
{
  if (!assignments.empty())
  {
    LOG(plog.crawl, HDR << "clearing assignments of " << this << std::endl);

    for (AI ii=assignments.begin(); ii != assignments.end(); ++ii)
      (*ii)->clear();
  }

  assignments.clear();
}

bool Value::dirtyChanged(SymbolTable *symbols, Value *rhs, bool mergeAssignments)
{
  bool retval = false;

  if (typeid(*this) != typeid(*rhs))
  {
    plog.err() << HDR << "Merging incompatible values " << typeid(*this).name() << " vs "
	       << typeid(*rhs).name() << std::endl;
    plog.err() << HDR << "With types " << type->toString() << " vs "
	       << rhs->type->toString() << std::endl;

    exit(-1);
  }

  /* Add rhs's assignments to our own */
  if (!rhs->assignments.empty())
  {
    for (AI ii=rhs->assignments.begin(); ii != rhs->assignments.end(); ++ii)
    {
      bool found=false;

      if (!assignments.empty())
      {
	for (AI jj=assignments.begin(); jj != assignments.end(); ++jj)
	{
	  if (*ii == *jj)
	  {
	    found = true;
	    break;
	  }
	}
      }

      if (!found)
      {
	if (mergeAssignments)
	{
	  bool outputTentative = g_outputTentative;
	  g_outputTentative = true;

	  LOG(plog.crawl, HDR << "Adding " << (*ii)->toString() << std::endl);

	  g_outputTentative = outputTentative;

	  addassignment(*ii);
	  retval = true;
	}
	known = false;
      }
    }
  }

  known &= rhs->known;

  return retval;
}

void Value::mergeAssignments(std::vector<Stat*> &_assignments)
{
  if (!_assignments.empty())
  {
    for (AI ii=_assignments.begin(); ii != _assignments.end(); ++ii)
    {
      bool found=false;

      if (!assignments.empty())
      {
	for (AI jj=assignments.begin(); jj != assignments.end(); ++jj)
	{
	  if (*ii == *jj)
	  {      
	    found = true;
	    break;
	  }
	}
      }

      if (!found)
	addassignment(*ii);
    }
  }
}

void Value::mergeDeclarations(std::vector<Declaration2*> &_declarations)
{
  if (!_declarations.empty())
  {
    for (DI ii=_declarations.begin(); ii != _declarations.end(); ++ii)
    {
      bool found=false;

      if (!declarations.empty())
      {
	for (DI jj=declarations.begin(); jj != declarations.end(); ++jj)
	{
	  if (*ii == *jj)
	  {      
	    found = true;
	    break;
	  }
	}
      }

      if (!found)
	adddeclaration(*ii);
    }
  }
}

/* ************************************************************************* */

Expression *LeftExpression::reduce(SymbolTable *symbols, Compound *out, Use use)
{
  LOG(plog.crawl, HDR << "reducing leftexpression " << toString() << " " << use
	       << std::endl);

  LeftExpression *work = this;

  LOG(plog.crawl, HDR << "work is " << work->toString() << std::endl);

  LeftExpression *route = work->buildStoragePath(symbols, out);

  LOG(plog.crawl, HDR << "storage path is " << route->toString() << std::endl);

  type = route->type;

  std::list<Value**> storage, path;
  work->findStorage(symbols, out, storage, path);

  LOG(plog.crawl, HDR << "storage size " << storage.size() << std::endl);
  if (storage.size() == 1)
    LOG(plog.crawl, HDR << "typeid " << typeid(**storage.front()).name() << " value "
		 << (*storage.front())->toString() << std::endl);

#if 0
  if (use == NotUsed)
  {
    /* Don't reduce if the value isn't going to be used */
    return new VoidValue();
  }
#endif

  if (storage.size() == 1 && typeid(**storage.front()) == typeid(ArrayValue) &&
      use != AsCode)
  {
    /* Array values are reduced as pointers to them, unless we're supposed to
       output a code value */
    Id *id = work->findId(symbols);
    Variable *var = dynamic_cast<Variable*>(symbols->findSymbol(id->name));
    if (!var)
      error(CStr("'") << id->name << "' is not a variable");

    delete id;

    PointerValue *ptr = new PointerValue(symbols, var->index, route);

    /* Set type to original type instead of pointer to it */
    ptr->type = work->type;

    LOG(plog.crawl, HDR << "leftexpression reduced to " << ptr->toString() << " type "
		 << ptr->type->toString() <<std::endl);

    return ptr;
  }

  if (storage.size() == 1 &&
      ((typeid(**storage.front()) != typeid(PointerValue) &&
        (*storage.front())->storageIsKnown(symbols, out, true)) ||
       (use != NotUsed &&
        (*storage.front())->storageIsKnown(symbols, out, false))))
  {
    /* There's only one possible storage, and it's known */
    Expression *res = (*storage.front())->reduce(symbols, out, use);
    
    Value *val = dynamic_cast<Value*>(res);
    
    /* Make sure this value doesn't cause a residualization of the
     * generating expression */
    if (val)
      val->removeGenerators();

    delete route;
    return res;
  }
  else
  {
    return route;
  }
}

void LeftExpression::residualize(SymbolTable *symbols)
{
  Compound *dummy = new Compound();

  std::list<Value**> storage, path;
  findStorage(symbols, dummy, storage, path);

  LOG(plog.debug, HDR << "residualizing leftexpression " << toString() << std::endl);
  LOG(plog.crawl, HDR << "residualizing intermediate variables" << std::endl);
  
  /* Residualize intermediate variables */
  if (!path.empty())
    for (SI ii = path.begin(); ii != path.end(); ++ii)
    {
      /* *** SHOULD CALL RESIDUALIZE WITH SOME PARAMETER TO AVOID RECURSION *** */
      if (!(**ii)->declarations.empty())
      {
	std::vector<Declaration2*> _declarations = (**ii)->declarations;
	(**ii)->declarations.clear();

	LOG(plog.crawl, HDR << "clearing declarations" << std::endl);

	for (Value::DI jj=_declarations.begin(); jj != _declarations.end(); ++jj)
	  (*jj)->residualize(symbols);
      }
      
      if (!(**ii)->assignments.empty())
      {
	std::vector<Stat*> _assignments = (**ii)->assignments;
	(**ii)->assignments.clear();

	LOG(plog.crawl, HDR << "clearing assignments" << std::endl);

	for (Value::AI jj=_assignments.begin(); jj != _assignments.end(); ++jj)
	  (*jj)->residualize(symbols);
      }
    }

  LOG(plog.crawl, HDR << "residualizing storage path" << std::endl);

  /* Residualize the expressions that lead to the path */
  residualizeStoragePath(symbols);
  
  LOG(plog.crawl, HDR << "residualizing storage locations" << std::endl);

  /* And residualize the storage locations themselves */
  if (!storage.empty())
    for (SI ii = storage.begin(); ii != storage.end(); ++ii)
      (**ii)->residualize(symbols);

  delete dummy;
}

void LeftExpression::setData(SymbolTable *symbols, Compound *out, Value *newdata)
{
  std::list<Value**> storage, path;

  findStorage(symbols, out, storage, path);

  if (storage.size() == 1)
  {
    /* There's only one possible storage, which means it's known  */
    Value **item = storage.front(), *olddata = *item;
    Type *type = (*item)->type;

    /* Gather path assignments */
    std::vector<Stat*> assignments;
    std::vector<Declaration2*> declarations;
    
    if (!path.empty())
    {
      for (SI ii=path.begin(); ii != path.end(); ++ii)
      {
	if (!(*(*ii))->declarations.empty())
	  for (Value::DI jj=(*(*ii))->declarations.begin();
	       jj != (*(*ii))->declarations.end(); ++jj)
	    declarations.push_back((*jj));
	
	if ((**ii) != (*item))
	  if (!(*(*ii))->assignments.empty())
	    for (Value::AI jj=(*(*ii))->assignments.begin();
		 jj != (*(*ii))->assignments.end(); ++jj)
	      assignments.push_back((*jj));
      }
    }
    
    if (!newdata->type->equals(type))
    {
      if (newdata->known &&
	  (typeid(*type) == typeid(IntegerType) ||
	   typeid(*type) == typeid(FloatType)) &&
	  (typeid(*newdata->type) == typeid(IntegerType) ||
	   typeid(*newdata->type) == typeid(FloatType)))
      {
	*item = type->makeValue(newdata->castToFloat());
	(*item)->mergeAssignments(newdata->assignments);
	(*item)->mergeDeclarations(newdata->declarations);

	/* Add to value */
	(*item)->mergeAssignments(assignments);
	(*item)->mergeDeclarations(declarations);
	
	delete newdata;
      }
      else
      {
#if 1
	plog.residualize() << HDR << "residualizing unknown type conversion "
			   << newdata->type->toString() << " -> " << type->toString() 
			   << std::endl;

	clearData(symbols, out);
	newdata->residualize(symbols);
#else
	/* See Assign::reduce for information about why this doesn't work */

	(*item)->assignments.clear();
	(*item)->known = false;

	if (!newdata->assignments.empty())
	  for (Value::AI ii=newdata->assignments.begin();
	       ii != newdata->assignments.end(); ++ii)
	    (*item)->addassignment(*ii);
#endif

	delete newdata;
	return;
      }
    }
    else
    {
      *item = newdata;

      /* Add to value */
      (*item)->mergeAssignments(assignments);
      (*item)->mergeDeclarations(declarations);
    }

    int outputTentative = g_outputTentative;
    g_outputTentative = true;

    LOG(plog.debug, HDR << "storage set to " << (*item) << " with assignment " << (*item)->assignments[0]->toString() << std::endl);

    g_outputTentative = outputTentative;

    delete olddata;
  }
  else
  {
    LOG(plog.debug, HDR << "storage not set to " << newdata << std::endl);

    /* The storage is unknown. */
    /* Mark all possible storage locations dirty */
    clearData(symbols, out);
 
    newdata->residualize(symbols);

    delete newdata;
  }
}

void LeftExpression::clearData(SymbolTable *symbols, Compound *out)
{
  std::list<Value**> storage, path;

  LOG(plog.debug, HDR << "Clearing " << toString() << std::endl);

  findStorage(symbols, out, storage, path);

  if (storage.size() == 1)
  {
    /* This data is going to be overwritten anyway, so there's no reason to
     * output the assignments */
    (*storage.front())->clearassignments();
  }

  /* Dump all data we know */
  if (!storage.empty())
    for (SI ii = storage.begin(); ii != storage.end(); ++ii)
      (**ii)->residualize(symbols, true);
}

/* ************************************************************************* */

Id *DecodeId(Code *did, SymbolTable *symbols, Compound *out)
{
  Id *id = dynamic_cast<Id*>(did);

  if (!id)
  {
    Decode *decode = dynamic_cast<Decode*>(did);

    if (!decode)
      error("Expecting Decode or Id");

    CodeValue *decoderes = dynamic_cast<CodeValue*>(decode->data->reduce(symbols, out, AsExpression));
    
    if (!decoderes)
      error("Decoding an expression yielding no code");
    
    id = dynamic_cast<Id*>(decoderes->data->copy());
    
    if (!id)
      error("Decoded expression must yield a coded identifier");
    
    delete decoderes;
  }
  else
    id = id->copy();  

  return id;
}
